package 动态规划.另类的;

import org.junit.Test;

import java.util.Arrays;
import java.util.Locale;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/21 9:13
 */
public class lc926将字符串翻转到单调递增 {




    /*
     前缀和 解法
     */
    int minFlipsMonoIncr(String s) {
        int n = s.length();
        int preSum[] = new int[n + 1];
        for(int i = 0; i < n; ++i)
            preSum[i+1] = preSum[i] + (s.charAt(i) - '0');

        int ans = Integer.MAX_VALUE;
        for(int i = 0; i <= n; ++i)
            ans = Math.min(ans, preSum[i] + (n-i - (preSum[n] - preSum[i])));
        //             ^^^^^^^^       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        //             当前字符前面1的数量    当前字符包括当前字符后面0的数量
        return ans;
    }











    public int solve(String s) {
        int len = s.length();

        int dp[][] = new int[len][2];
        dp[len - 1][0] = s.charAt(len - 1) == '0' ? 0 : 1;
        dp[len - 1][1] = s.charAt(len - 1) == '0' ? 1 : 0;

        for(int i = len - 2;i >= 0 ;i--){
            dp[i][0] = Math.min(dp[i + 1][0],dp[i + 1][1]) + (s.charAt(i) == '0' ? 0 : 1);
            dp[i][1] = dp[i + 1][1] + (s.charAt(i) == '1' ? 0 : 1);
        }
        return Math.min(dp[0][0],dp[0][1]);
    }
    /*
     这个 是真的 绕 啊 这个 dp
     f（index， 0） 表示： 从 index ~ len ，并且 当前 以0 开头 的 递增最小修改次数
     f（index， 1） 表示： 从 index ~ len ，并且 当前 以 1 开头 的 递增最小修改次数

    ** 注意 当前 以 0 开头 并不代表 当前元素是 0 ， nums[index] 可能是0  也可能是 1 修改成的 0 **
    这是理解 明白 最核心的一句话

     */
    public int recursion(int index,int state,char nums[],Integer dp[][]){
        if(index == nums.length){
            return 0;
        }
        if(dp[index][state] != null){
            return dp[index][state];
        }
        int ans = 0;
        if(state == 0){ //  注意 当前 以 0 开头 并不代表 当前元素是 0 ， nums[index] 可能是0  也可能是 1 修改成的 0
            ans = Math.min(recursion(index + 1,0,nums,dp),recursion(index + 1,1,nums,dp)) + (nums[index] == '0' ? 0 : 1);
        }else{ // 当前是 1  ,可能 nums[index] 本身是 1 , 或者 是从 0 修改成的 1
            // 是 1  ,后面的 字符 只能是 1
            ans = recursion(index + 1,1,nums,dp) + (nums[index] == '0' ? 1 : 0);
        }
        return dp[index][state] = ans;
    }

    public int solution(String s ){
        char[] nums = s.toCharArray();
        Integer dp[][] = new Integer[nums.length][2];
        return Math.min(recursion(0,0,nums,dp),recursion(0,1,nums,dp));
    }


    @Test
    public void test(){
        String s = "00110";
        System.out.println(solve(s));
    }

}
